package com.wenhai.leetcode.sort;

import java.util.Arrays;
import java.util.Random;

/**
 *https://leetcode-cn.com/problems/smallest-k-lcci/
 *
 * @author wenhai
 * @date   2021/3/1
 */
public class _面试题1714最小K个数 {
    private static final Random RANDOM = new Random();

    public int[] smallestK(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }
        this.selectK(arr, 0, arr.length - 1, k - 1);
        int[] resArr = Arrays.copyOf(arr, k);
        System.gc();
        return resArr;
    }

    private void selectK(int[] arr, int l, int r, int k) {
        int p = partition(arr, l, r);
        if (p == k) {
            return;
        }
        if (p > k) {
            selectK(arr, l, p - 1, k);
            return;
        }
        selectK(arr, p + 1, r, k);
    }

    private int partition(int[] arr, int l, int r) {
        if (l >= r) {
            return l;
        }

        int p = l + RANDOM.nextInt(r - l + 1);
        swap(arr, l, p);
        int i = l + 1;
        int j = r;
        while (true){
            while (i <= j && arr[i] < arr[l]) {
                i++;
            }
            while (j >= i && arr[j] > arr[l]) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(arr, i, j);
            j--;
            i++;
        }
        swap(arr, l, j);
        return j;
    }
    private void swap(int[] nums, int srcPos, int destPos) {
        int temp = nums[srcPos];
        nums[srcPos] = nums[destPos];
        nums[destPos] = temp;
    }


}
